package algorithm;

public class leetcode_0063 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int [][] dp=new int[m][n];
        for(int i=0;i<m;++i){
            dp[i][0]=1;
            if(obstacleGrid[i][0]==1) {dp[i][0]=0;break;}
        }
        for(int j=0;j<n;++j){
            dp[0][j]=1;
            if(obstacleGrid[0][j]==1) {dp[0][j]=0;break;}
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
                if(obstacleGrid[i][j]==1) dp[i][j]=0;
            }
        }
        return dp[m-1][n-1];
    }
}
